package _dp_base;

/**
 * 1137. 第 N 个泰波那契数
 */
public class No1137 {
    /**
     * 1. 递归
     */
    public int tribonacci(int n) {
        return dfs(n);
    }

    private int dfs(int i) {
        if (i <= 0) return 0;
        else if (i == 1 || i == 2) return 1;
        else return dfs(i - 3) + dfs(i - 2) + dfs(i - 1);
    }

    /**
     * 2. 迭代
     */
    public int tribonacci2(int n) {
        if (n == 0) return 0;
        else if (n == 1 || n == 2) return 1;
        int[] f = new int[n + 4];
        f[0] = 0;
        f[1] = 1;
        f[2] = 1;
        for (int i = 0; i <= n; i++) {
            f[i + 3] = f[i] + f[i + 1] + f[i + 2];
        }
        return f[n];
    }

    /**
     * 3. 空间优化
     */
    public int tribonacci3(int n) {
        int f0 = 0, f1 = 1, f2 = 1;
        for (int i = 0; i < n; i++) {
            int temp1 = f1, temp2 = f2;
            f2 = f0 + f1 + f2;
            f1 = temp2;
            f0 = temp1;
        }
        return f0;
    }
}
